// https://www.bilibili.com/video/BV1AA411B7XV/?spm_id_from=333.788.videocard.5

class Solution
{
public:
  string longestPalindrome(string s)
  {
    int len = s.length();

    if (len < 1)
      return nullptr;

    // 1. 定义一个 dp[i][j] 二维数组
    // - dp[i][j] == 0 表示 s[i] ~ s[j] 子串【不是】一个回文子串
    // - dp[i][j] == 1 表示 s[i] ~ s[j] 子串【是】一个回文子串
    vector<vector<int>> dp(len, vector<int>(len));

    // 2. dp[i,i]
    // - 表示 s[i] 到 s[i] 其实就是 s[i] 自己一个字符
    // - 因为【一个】字符的子串，肯定是一个【回文串】
    // - 所以 dp[i][i] = 1 表示 s[i] 就是一个【回文串】
    for (size_t i = 0; i < len; i++)
      dp[i][i] = 1;

    // 3. 处理 剩下的  s[i] 到 s[j] 子串
    int max_len = 1; // 记录【最大】的回文子串的【长度】，默认 1（因为第一个字符，一个字符，肯定是回文子串）
    int start = 0; // 从 s[0] 开始遍历
    for (int j = 1; j < len; j++) // j 从 1开始，因为 str[0, 0] 就是 str[0] 一个字符，肯定是【回文串】
    {
      for (int i = 0; i < (len - 1) && i < j; i++) // i: 0 => j-1（i 遍历 j 前面的字符）
      {
      	// 更新 dp[i][j]
        if (s[i] != s[j]) // s[i,j] 肯定【不是】回文子串. 比如 ab
        {
          dp[i][j] = 0;
        }
        else
        {
          // 此时虽然 s[i] == s[j] 但是还需要继续判断 i..j【之间】的字符，是不是回文字符串
          if ((j-i+1) < 4) // 不超过3个字符（aba、aa）情况，肯定是回文串
          {
            dp[i][j] = 1;
          }
          else
          {
            // 就需要继续判断【子串】是否是回文串
            dp[i][j] = dp[i + 1][j - 1]; // i往后走，j往前走
          }
        }

        // 更新 最大回文子串 start 和 mex_len
        if (dp[i][j])
        {
          max_len = max(j - i + 1, max_len);// 最大的【长度】
          start = i; // 最新的【起始】下标
        }
      }
    }

    // 4. 返回【最大】回文子串
    return s.substr(start, start + max_len)
  }
};